//
//  Trie.swift
//  LLTryFightingApp
//
//  Created by jinbang.li on 2024/9/28.
//

import Foundation
class TrieNode {
    var children:[Character:TrieNode]
    var isEndOfWord: Bool
    
    init() {
        self.children = [:]
        self.isEndOfWord = false
    }
}
class Trie {
    private var root:TrieNode
    
    init() {
        self.root = TrieNode()
    }
    ///插入单词
    func insert(_ word:String) {
        var currenyNode = root
        for character in word {
            if currenyNode.children[character] == nil {
                currenyNode.children[character] = TrieNode()
            }
            currenyNode = currenyNode.children[character]!
        }
        currenyNode.isEndOfWord = true
    }
    
    ///查找单词
    func search(_ word:String) -> Bool {
        var currentNode = root
        for character in word {
            guard let nextNode = currentNode.children[character] else
            { return false }
            currentNode = nextNode
        }
        return currentNode.isEndOfWord
    }
    
    //查找前缀
    func startsWith(_ prefix: String) ->Bool {
        var currentNode = root
        for character in prefix {
            guard let nextNode = currentNode.children[character] else
            { return false }
            currentNode = nextNode
        }
        return true
    }
}
